/*
https://leetcode.cn/problems/sparse-similarity-lcci/solution/c-yuan-shu-jie-fa-shi-xian-ha-xi-biao-by-wen-zhong/
 */
import java.util.*;

public class SolutionInterview17_26 {
    public List<String> computeSimilarities(int[][] docs) {
        List<String> ans=new ArrayList<>();
        List<Integer>[] map= new List[100000];
        int[][] f=new int[docs.length][docs.length];
        for (int i = 0; i < map.length; i++) {
            map[i]=new ArrayList<>();
        }
        for (int i=0;i<docs.length;i++){
            for (int i1 : docs[i]) {
                for (Integer integer : map[i1]) {
                    f[integer][i]++;
                }
                map[i1].add(i);
            }
        }
        for (int i=0;i<docs.length;i++){
            for (int j=i+1;j<docs.length;j++){
                if (f[i][j]>0){
                    ans.add(String.valueOf(i) + ',' + j + ": " + String.format("%.4f",(1.0*f[i][j])/(docs[i].length+docs[j].length-f[i][j])));
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview17_26().computeSimilarities(new int[][]{{14, 15, 100, 9, 3},{32, 1, 9, 3, 5},{15, 29, 2, 6, 8, 7},{7, 10}}));
    }
}
